#ifndef CLIB_RBTREE_H
#define CLIB_RBTREE_H

#pragma once

#ifdef __cplusplus
extern "C" {
#endif

#include "clib_type.h"

#define rbnode_red    0
#define rbnode_black  1

typedef struct rb_node {
	
    u64_t           clocr:4;
    u64_t           rb_parent:60;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} rbnode_t;

typedef struct rb_root {
	struct rb_node *root;
} rbtree_t;

typedef int  (*rbnode_cmp_fn)(const rbnode_t *old, const rbnode_t *node);

typedef int  (*rbtree_find_fn)(const rbnode_t *node,void *key);

#define rb_get_parent(node) (rbnode_t*)(node)->rb_parent

#define rb_set_parent(one,two) (one)->rb_parent = (u64_t)(two)

#define rb_color(node)      ((node)->clocr)

#define rb_is_red(node)     (!rb_color(node))

#define rb_is_black(node)   rb_color(node)

#define rb_set_red(node)    do { (node)->clocr = rbnode_red; } while (0)

#define rb_set_black(node)  do { (node)->clocr = rbnode_black; } while (0)

#define rbnode_init(node)   do                                  \
                            {                                   \
                                (node)->clocr      = 0;         \
                                (node)->rb_parent  = 0;         \
                                (node)->rb_right   = 0;         \
                                (node)->rb_left    = 0;         \
                            } while(0)

i32_t
rb_add(rbtree_t *rbtree,rbnode_t *rbnode,rbnode_cmp_fn less);

i32_t
rb_del(rbtree_t *rbtree,rbnode_t *rbnode);


rbnode_t *rb_find(rbtree_t *rbtree,void *key,rbtree_find_fn look_up);

rbnode_t *rb_first(rbtree_t *rbtree);

rbnode_t *rb_last (rbtree_t *rbtree);

rbnode_t *rb_next (rbnode_t *rbnode);

rbnode_t *rb_prev (rbnode_t *rbnode);

/*************************************************************************/
/* Macros that define a red-black tree */
#define rbt_head(name, type)												\
	struct name {															\
		struct type *rbh_root; /* root of the tree */						\
	}
	
#define rbt_initiallzer(root)												\
		{ NULL }
	
#define rbt_init(root) do {													\
		(root)->rbh_root = NULL;											\
	} while (0)


#define rbt_black	0
#define rbt_red		1

#define rbt_entry(type)														\
struct {																	\
	struct type *rbt_left;		/* left element */							\
	struct type *rbt_right;		/* right element */							\
	struct type *rbt_parent;	/* parent element */						\
	int rbt_color;				/* node color */							\
}

#define rbt_left(elm, field)		(elm)->field.rbt_left
#define rbt_right(elm, field)		(elm)->field.rbt_right
#define rbt_parent(elm, field)		(elm)->field.rbt_parent
#define rbt_color(elm, field)		(elm)->field.rbt_color
#define rbt_root(head)				(head)->rbh_root
#define rbt_empty(head)				(rbt_root(head) == NULL)

#define rbt_set(elm, parent, field) do {										\
	rbt_parent(elm, field) = parent;											\
	rbt_left(elm, field) = rbt_right(elm, field) = NULL;						\
	rbt_color(elm, field) = rbt_red;											\
} while (0)					
					
#define rbt_set_blackread(black, red, field) do {								\
	rbt_color(black, field) = rbt_black;										\
	rbt_color(red, field) = rbt_red;											\
} while (0)

#ifndef rbt_augment
#define rbt_augment(x)	do {} while (0)
#endif



#define rbt_rotate_left(head, elm, tmp, field) do {							\
	(tmp) = rbt_right(elm, field);											\
	if ((rbt_right(elm, field) = rbt_left(tmp, field)) != NULL) {			\
		rbt_parent(rbt_left(tmp, field), field) = (elm);					\
	}																		\
	rbt_augment(elm);														\
	if ((rbt_parent(tmp, field) = rbt_parent(elm, field)) != NULL) {		\
		if ((elm) == rbt_left(rbt_parent(elm, field), field))				\
			rbt_left(rbt_parent(elm, field), field) = (tmp);				\
		else																\
			rbt_right(rbt_parent(elm, field), field) = (tmp);				\
	} else																	\
		(head)->rbh_root = (tmp);											\
	rbt_left(tmp, field) = (elm);											\
	rbt_parent(elm, field) = (tmp);											\
	rbt_augment(tmp);														\
	if ((rbt_parent(tmp, field)))											\
		rbt_augment(rbt_parent(tmp, field));								\
} while (0)			
			
				
#define rbt_rotate_right(head, elm, tmp, field) do {						\
		(tmp) = rbt_left(elm, field);										\
		if ((rbt_left(elm, field) = rbt_right(tmp, field)) != NULL) { 		\
			rbt_parent(rbt_right(tmp, field), field) = (elm); 				\
		}																	\
		rbt_augment(elm);													\
		if ((rbt_parent(tmp, field) = rbt_parent(elm, field)) != NULL) {	\
			if ((elm) == rbt_left(rbt_parent(elm, field), field)) 			\
				rbt_left(rbt_parent(elm, field), field) = (tmp);			\
			else															\
				rbt_right(rbt_parent(elm, field), field) = (tmp); 			\
		} else																\
			(head)->rbh_root = (tmp);										\
		rbt_right(tmp, field) = (elm);										\
		rbt_parent(elm, field) = (tmp);										\
		rbt_augment(tmp);													\
		if ((rbt_parent(tmp, field)))										\
			rbt_augment(rbt_parent(tmp, field));							\
	} while (0)


#define	rbt_prototype(name, type, field, cmp)								\
			RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define	rbt_prototype_static(name, type, field, cmp)						\
			RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define rbt_prototype_internal(name, type, field, cmp, attr)				\
		attr void name##_rb_insert_color(struct name *, struct type *); 	\
		attr void name##_rb_remove_color(struct name *, struct type *, struct type *);\
		attr struct type *name##_rb_remove(struct name *, struct type *);	\
		attr struct type *name##_rb_insert(struct name *, struct type *);	\
		attr struct type *name##_rb_find(struct name *, struct type *); 	\
		attr struct type *name##_rb_nfind(struct name *, struct type *);	\
		attr struct type *name##_rb_next(struct type *);					\
		attr struct type *name##_rb_prev(struct type *);					\
		attr struct type *name##_rb_minmax(struct name *, int); 			\

/* Main rb operation.
 * Moves node close to the key of elm to top
 */
#define	rbt_generate(name, type, field, cmp)								\
	rbt_generate_internal(name, type, field, cmp,)
#define	RB_GENERATE_STATIC(name, type, field, cmp)							\
	rbt_generate_internal(name, type, field, cmp, static)
#define rbt_generate_internal(name, type, field, cmp, attr)					\
attr void																	\
name##_rb_insert_color(struct name *head, struct type *elm)	{				\
	struct type *parent, *gparent, *tmp;									\
	while ((parent = rbt_parent(elm, field)) != NULL &&						\
	    rbt_color(parent, field) == rbt_red) {								\
		gparent = rbt_parent(parent, field);								\
		if (parent == rbt_left(gparent, field)) {							\
			tmp = rbt_right(gparent, field);								\
			if (tmp && rbt_color(tmp, field) == rbt_red) {					\
				rbt_color(tmp, field) = rbt_black;							\
				rbt_set_blackread(parent, gparent, field);					\
				elm = gparent;												\
				continue;													\
			}																\
			if (rbt_right(parent, field) == elm) {							\
				rbt_rotate_left(head, parent, tmp, field);					\
				tmp = parent;												\
				parent = elm;												\
				elm = tmp;													\
			}																\
			rbt_set_blackread(parent, gparent, field);						\
			rbt_rotate_right(head, gparent, tmp, field);					\
		} else {															\
			tmp = rbt_left(gparent, field);									\
			if (tmp && rbt_color(tmp, field) == rbt_red) {					\
				rbt_color(tmp, field) = rbt_black;							\
				rbt_set_blackread(parent, gparent, field);					\
				elm = gparent;												\
				continue;													\
			}																\
			if (rbt_left(parent, field) == elm) {							\
				rbt_rotate_right(head, parent, tmp, field);					\
				tmp = parent;												\
				parent = elm;												\
				elm = tmp;													\
			}																\
			rbt_set_blackread(parent, gparent, field);						\
			rbt_rotate_left(head, gparent, tmp, field);						\
		}																	\
	}																		\
	rbt_color(head->rbh_root, field) = rbt_black;							\
}																			\
																			\
attr void																	\
name##_rb_remove_color(struct name *head, struct type *parent, struct type *elm) \
{																			\
	struct type *tmp;														\
	while ((elm == NULL || rbt_color(elm, field) == rbt_black) &&			\
	    elm != rbt_root(head)) {											\
		if (rbt_left(parent, field) == elm) {								\
			tmp = rbt_right(parent, field);									\
			if (rbt_color(tmp, field) == rbt_red) {							\
				rbt_set_blackread(tmp, parent, field);						\
				rbt_rotate_left(head, parent, tmp, field);					\
				tmp = rbt_right(parent, field);								\
			}																\
			if ((rbt_left(tmp, field) == NULL ||							\
			    rbt_color(rbt_left(tmp, field), field) == rbt_black) &&		\
			    (rbt_right(tmp, field) == NULL ||							\
			    rbt_color(rbt_right(tmp, field), field) == rbt_black)) {	\
				rbt_color(tmp, field) = rbt_red;							\
				elm = parent;												\
				parent = rbt_parent(elm, field);							\
			} else {														\
				if (rbt_right(tmp, field) == NULL ||						\
				    rbt_color(rbt_right(tmp, field), field) == rbt_black) {	\
					struct type *oleft;										\
					if ((oleft = rbt_left(tmp, field)) 						\
					    != NULL)											\
						rbt_color(oleft, field) = rbt_black;				\
					rbt_color(tmp, field) = rbt_red;						\
					rbt_rotate_right(head, tmp, oleft, field);				\
					tmp = rbt_right(parent, field);							\
				}															\
				rbt_color(tmp, field) = rbt_color(parent, field);			\
				rbt_color(parent, field) = rbt_black;						\
				if (rbt_right(tmp, field))									\
					rbt_color(rbt_right(tmp, field), field) = rbt_black;	\
				rbt_rotate_left(head, parent, tmp, field);					\
				elm = rbt_root(head);										\
				break;														\
			}																\
		} else {															\
			tmp = rbt_left(parent, field);									\
			if (rbt_color(tmp, field) == rbt_red) {							\
				rbt_set_blackread(tmp, parent, field);						\
				rbt_rotate_right(head, parent, tmp, field);					\
				tmp = rbt_left(parent, field);								\
			}																\
			if ((rbt_left(tmp, field) == NULL ||							\
			    rbt_color(rbt_left(tmp, field), field) == rbt_black) &&		\
			    (rbt_right(tmp, field) == NULL ||							\
			    rbt_color(rbt_right(tmp, field), field) == rbt_black)) {	\
				rbt_color(tmp, field) = rbt_red;							\
				elm = parent;												\
				parent = rbt_parent(elm, field);							\
			} else {														\
				if (rbt_left(tmp, field) == NULL ||							\
				    rbt_color(rbt_left(tmp, field), field) == rbt_black) {	\
					struct type *oright;									\
					if ((oright = rbt_right(tmp, field)) 					\
					    != NULL)											\
						rbt_color(oright, field) = rbt_black;				\
					rbt_color(tmp, field) = rbt_red;						\
					rbt_rotate_left(head, tmp, oright, field);				\
					tmp = rbt_left(parent, field);							\
				}															\
				rbt_color(tmp, field) = rbt_color(parent, field);			\
				rbt_color(parent, field) = rbt_black;						\
				if (rbt_left(tmp, field))									\
					rbt_color(rbt_left(tmp, field), field) = rbt_black;		\
				rbt_rotate_right(head, parent, tmp, field);					\
				elm = rbt_root(head);										\
				break;														\
			}																\
		}																	\
	}																		\
	if (elm)																\
		rbt_color(elm, field) = rbt_black;									\
}																			\
																			\
attr struct type *															\
name##_rb_remove(struct name *head, struct type *elm)						\
{																			\
	struct type *child, *parent, *old = elm;								\
	int color;																\
	if (rbt_left(elm, field) == NULL)										\
		child = rbt_right(elm, field);										\
	else if (rbt_right(elm, field) == NULL)									\
		child = rbt_left(elm, field);										\
	else {																	\
		struct type *left;													\
		elm = rbt_right(elm, field);										\
		while ((left = rbt_left(elm, field)) != NULL)						\
			elm = left;														\
		child = rbt_right(elm, field);										\
		parent = rbt_parent(elm, field);									\
		color = rbt_color(elm, field);										\
		if (child)															\
			rbt_parent(child, field) = parent;								\
		if (parent) {														\
			if (rbt_left(parent, field) == elm)								\
				rbt_left(parent, field) = child;							\
			else															\
				rbt_right(parent, field) = child;							\
			rbt_augment(parent);											\
		} else																\
			rbt_root(head) = child;											\
		if (rbt_parent(elm, field) == old)									\
			parent = elm;													\
		(elm)->field = (old)->field;										\
		if (rbt_parent(old, field)) {										\
			if (rbt_left(rbt_parent(old, field), field) == old)				\
				rbt_left(rbt_parent(old, field), field) = elm;				\
			else															\
				rbt_right(rbt_parent(old, field), field) = elm;				\
			rbt_augment(rbt_parent(old, field));							\
		} else																\
			rbt_root(head) = elm;											\
		rbt_parent(rbt_left(old, field), field) = elm;						\
		if (rbt_right(old, field))											\
			rbt_parent(rbt_right(old, field), field) = elm;					\
		if (parent) {														\
			left = parent;													\
			do {															\
				rbt_augment(left);											\
			} while ((left = rbt_parent(left, field)) != NULL); 			\
		}																	\
		goto color;															\
	}																		\
	parent = rbt_parent(elm, field);										\
	color = rbt_color(elm, field);											\
	if (child)																\
		rbt_parent(child, field) = parent;									\
	if (parent) {															\
		if (rbt_left(parent, field) == elm)									\
			rbt_left(parent, field) = child;								\
		else																\
			rbt_right(parent, field) = child;								\
		rbt_augment(parent);												\
	} else																	\
		rbt_root(head) = child;												\
color:																		\
	if (color == rbt_black)													\
		name##_rb_remove_color(head, parent, child);						\
	return (old);															\
}																			\
																			\
/* Inserts a node into the RB tree */										\
attr struct type *															\
name##_rb_insert(struct name *head, struct type *elm) {						\
	struct type *tmp;														\
	struct type *parent = NULL;												\
	int comp = 0;															\
	tmp = rbt_root(head);													\
	while (tmp) {															\
		parent = tmp;														\
		comp = (cmp)(elm, parent);											\
		if (comp < 0)														\
			tmp = rbt_left(tmp, field);										\
		else if (comp > 0)													\
			tmp = rbt_right(tmp, field);									\
		else																\
			return (tmp);													\
	}																		\
	rbt_set(elm, parent, field);											\
	if (parent != NULL) {													\
		if (comp < 0)														\
			rbt_left(parent, field) = elm;									\
		else																\
			rbt_right(parent, field) = elm;									\
		rbt_augment(parent);												\
	} else																	\
		rbt_root(head) = elm;												\
	name##_rb_insert_color(head, elm);										\
	return (NULL);															\
}																			\
																			\
/* Finds the node with the same key as elm */								\
attr struct type *															\
name##_rb_find(struct name *head, struct type *elm)	{						\
	struct type *tmp = rbt_root(head);										\
	int comp;																\
	while (tmp) {															\
		comp = cmp(elm, tmp);												\
		if (comp < 0)														\
			tmp = rbt_left(tmp, field);										\
		else if (comp > 0)													\
			tmp = rbt_right(tmp, field);									\
		else																\
			return (tmp);													\
	}																		\
	return (NULL);															\
}																			\
																			\
/* Finds the first node greater than or equal to the search key */			\
attr struct type *															\
name##_rb_nfind(struct name *head, struct type *elm)						\
{																			\
	struct type *tmp = rbt_root(head);										\
	struct type *res = NULL;												\
	int comp;																\
	while (tmp) {															\
		comp = cmp(elm, tmp);												\
		if (comp < 0) {														\
			res = tmp;														\
			tmp = rbt_left(tmp, field);										\
		}																	\
		else if (comp > 0)													\
			tmp = rbt_right(tmp, field);									\
		else																\
			return (tmp);													\
	}																		\
	return (res);															\
}																			\
																			\
/* ARGSUSED */																\
attr struct type *															\
name##_rb_next(struct type *elm)											\
{																			\
	if (rbt_right(elm, field)) {											\
		elm = rbt_right(elm, field);										\
		while (rbt_left(elm, field))										\
			elm = rbt_left(elm, field);										\
	} else {																\
		if (rbt_parent(elm, field) &&										\
		    (elm == rbt_left(rbt_parent(elm, field), field)))				\
			elm = rbt_parent(elm, field);									\
		else {																\
			while (rbt_parent(elm, field) &&								\
			    (elm == rbt_right(rbt_parent(elm, field), field)))			\
				elm = rbt_parent(elm, field);								\
			elm = rbt_parent(elm, field);									\
		}																	\
	}																		\
	return (elm);															\
}																			\
																			\
/* ARGSUSED */																\
attr struct type *															\
name##_rb_prev(struct type *elm)											\
{																			\
	if (rbt_left(elm, field)) {												\
		elm = rbt_left(elm, field);											\
		while (rbt_right(elm, field))										\
			elm = rbt_right(elm, field);									\
	} else {																\
		if (rbt_parent(elm, field) &&										\
		    (elm == rbt_right(rbt_parent(elm, field), field)))				\
			elm = rbt_parent(elm, field);									\
		else {																\
			while (rbt_parent(elm, field) &&								\
			    (elm == rbt_left(rbt_parent(elm, field), field)))			\
				elm = rbt_parent(elm, field);								\
			elm = rbt_parent(elm, field);									\
		}																	\
	}																		\
	return (elm);															\
}																			\
																			\
attr struct type *															\
name##_rb_minmax(struct name *head, int val)								\
{																			\
	struct type *tmp = rbt_root(head);										\
	struct type *parent = NULL;												\
	while (tmp) {															\
		parent = tmp;														\
		if (val < 0)														\
			tmp = rbt_left(tmp, field);										\
		else																\
			tmp = rbt_right(tmp, field);									\
	}																		\
	return (parent);														\
}


#define rbt_insert(name, x, y)		name##_rb_insert(x, y)
#define rbt_remove(name, x, y)		name##_rb_remove(x, y)
#define rbt_find(name, x, y)		name##_rb_find(x, y)
#define rbt_next_get(name, x, y)	name##_rb_nfind(x, y)
#define rbt_next(name, x, y)		name##_rb_next(y)
#define rbt_prev(name, x, y)		name##_rb_prev(y)
#define rbt_first(name, x)			name##_rb_minmax(x, -1)
#define rbt_last(name, x)			name##_rb_minmax(x,  1)

#define rbt_foreach(x, name, head)											\
	for ((x) = rbt_first(name, head);										\
	     (x) != NULL;														\
	     (x) = name##_rb_next(x))

#define rbt_foreach_from(x, name, y)										\
	for ((x) = (y);															\
	    ((x) != NULL) && ((y) = name##_rb_next(x), (x) != NULL);			\
	     (x) = (y))

#define rbt_foreach_safe(x, name, head, y)									\
	for ((x) = rbt_first(name, head);										\
	    ((x) != NULL) && ((y) = name##_rb_next(x), (x) != NULL);			\
	     (x) = (y))

#define rbt_foreach_reverse(x, name, head)									\
	for ((x) = rbt_last(name, head);										\
	     (x) != NULL;														\
	     (x) = name##_rb_prev(x))

#define rbt_foreach_reverse_from(x, name, y)								\
	for ((x) = (y);															\
	    ((x) != NULL) && ((y) = name##_rb_prev(x), (x) != NULL);			\
	     (x) = (y))

#define rbt_foreach_reverse_safe(x, name, head, y)							\
	for ((x) = rbt_last(name, head);										\
	    ((x) != NULL) && ((y) = name##_rb_prev(x), (x) != NULL);			\
	     (x) = (y))

/**************************************************************************/

#ifdef __cplusplus
}
#endif
 
#endif